/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/find-the-duplicate-number
   @Language: C++
   @Datetime: 19-06-05 10:51
   */

// Method 1, binary search, Time O(nlogn), Time 2013ms
class Solution {
public:
	/**
	 * @param nums: an array containing n + 1 integers which is between 1 and n
	 * @return: the duplicate one
	 */
	int findDuplicate(vector<int> &nums) {
		// write your code here
		int begin=0, end=nums.size();
		while(begin<end){
			int mid=(end+begin)/2, cnt=0;
			for(int i=nums.size(); i--; cnt+=nums[i]<=mid);
			if(cnt<=mid) begin=mid+1;
			else end=mid;
		}
		return begin;
	}
};

// Method 2, cycle search, Time O(n), Time 3625ms
class Solution {
public:
	/**
	 * @param nums: an array containing n + 1 integers which is between 1 and n
	 * @return: the duplicate one
	 */
	int findDuplicate(vector<int> &nums) {
		// write your code here
		int i=0, j=0, k=0;
		do{
			i=nums[i];
			j=nums[nums[j]];
		}while(i!=j);
		do{
			i=nums[i];
			k=nums[k];
		}while(i!=k);
		return i;
	}
};

// Method 3, bit, Time O(32n), Time 3873ms
class Solution {
public:
	/**
	 * @param nums: an array containing n + 1 integers which is between 1 and n
	 * @return: the duplicate one
	 */
	int findDuplicate(vector<int> &nums) {
		// write your code here
		int res=0;
		for(int i=0; i<32; ++i){
			int bit=(1<<i), cnt=0;
			for(int j=nums.size(); j--; ){
				if(nums[j]&bit) ++cnt;
				if(j&bit) --cnt;
			}
			if(cnt>0) res+=bit;
		}
		return res;
	}
};

// Method 4, move nums, Time 1685ms
class Solution {
public:
	/**
	 * @param nums: an array containing n + 1 integers which is between 1 and n
	 * @return: the duplicate one
	 */
	int findDuplicate(vector<int> &nums) {
		// write your code here
		for(int i=0; i<nums.size();){
			if(nums[i]==nums[nums[i]]) return nums[i];
			swap(nums[i],nums[nums[i]]);
			if(nums[i]==i) ++i;
		}
		return -1;
	}
};
